def sqrt(number):
    """
    Calculate the floored square root of a number

    Args:
       number(int): Number to find the floored squared root
    Returns:
       int: Floored Square Root
    """
    if number < 0:
        return None  # Return None for negative numbers
    if number == 0 or number == 1:
        return number  # The square root of 0 and 1 is the number itself
    
    start = 0
    end = number
    while start <= end:
        mid = (start + end) // 2
        if mid * mid == number:
            return mid
        elif mid * mid < number:
            start = mid + 1
            result = mid
        else:
            end = mid - 1
    return result

# Test cases
print("Pass" if (3 == sqrt(9)) else "Fail")
print("Pass" if (0 == sqrt(0)) else "Fail")
print("Pass" if (4 == sqrt(16)) else "Fail")
print("Pass" if (1 == sqrt(1)) else "Fail")
print("Pass" if (5 == sqrt(27)) else "Fail")

Pass
Pass
Pass
Pass
Pass

def rotated_array_search(input_list, number):
    """
    Find the index by searching in a rotated sorted array

    Args:
       input_list(array), number(int): Input array to search and the target
    Returns:
       int: Index or -1
    """
    if not input_list:
        return -1
    
    start, end = 0, len(input_list) - 1
    
    while start <= end:
        mid = (start + end) // 2
        if input_list[mid] == number:
            return mid
        
        # If the left half is sorted
        if input_list[start] <= input_list[mid]:
            if input_list[start] <= number < input_list[mid]:
                end = mid - 1
            else:
                start = mid + 1
        # If the right half is sorted
        else:
            if input_list[mid] < number <= input_list[end]:
                start = mid + 1
            else:
                end = mid - 1
                
    return -1

def linear_search(input_list, number):
    for index, element in enumerate(input_list):
        if element == number:
            return index
    return -1

def test_function(test_case):
    input_list = test_case[0]
    number = test_case[1]
    if linear_search(input_list, number) == rotated_array_search(input_list, number):
        print("Pass")
    else:
        print("Fail")

# Test cases
test_function([[6, 7, 8, 9, 10, 1, 2, 3, 4], 6])
test_function([[6, 7, 8, 9, 10, 1, 2, 3, 4], 1])
test_function([[6, 7, 8, 1, 2, 3, 4], 8])
test_function([[6, 7, 8, 1, 2, 3, 4], 1])
test_function([[6, 7, 8, 1, 2, 3, 4], 10])

Pass
Pass
Pass
Pass
Pass

def rearrange_digits(input_list):
    """
    Rearrange Array Elements so as to form two number such that their sum is maximum.

    Args:
       input_list(list): Input List
    Returns:
       (int, int): Two maximum sums
    """
    # Sort numbers in descending order
    sorted_list = sorted(input_list, reverse=True)
    # Generate two numbers
    num1 = int("".join(map(str, sorted_list[0::2])))
    num2 = int("".join(map(str, sorted_list[1::2])))
    return (num1, num2)

# Test Cases
print(rearrange_digits([1, 2, 3, 4, 5]))  # Outputs: (531, 42)

**References:**

- "Greedy Algorithm." Wikipedia, the free encyclopedia, [Greedy Algorithm on Wikipedia](https://en.wikipedia.org/wiki/Greedy_algorithm). Accessed 21 May 2024.


**Solution:**

def rearrange_digits(input_list):
    """
    Rearrange array elements so as to form two numbers such that their sum is maximum.

    Args:
       input_list(list): Input List
    Returns:
       (int)(int): Two maximum sums
    """
    if not input_list:
        return [0, 0]
    
    input_list.sort(reverse=True)
    
    num1, num2 = '', ''
    for i in range(len(input_list)):
        if i % 2 == 0:
            num1 += str(input_list[i])
        else:
            num2 += str(input_list[i])
    
    return [int(num1), int(num2)]

def test_function(test_case):
    output = rearrange_digits(test_case[0])
    solution = test_case[1]
    if sum(output) == sum(solution):
        print("Pass")
    else:
        print("Fail")

# Test cases
test_function([[1, 2, 3, 4, 5], [542, 31]])
test_function([[4, 6, 2, 5, 9, 8], [964, 852]])

Pass
Pass

def sort_012(input_list):
    """
    Given an input array consisting only of 0, 1, and 2 sort the array in a single traversal.

    Args:
       input_list(list): List to be sorted
    """
    low = mid = 0
    high = len(input_list) - 1
    while mid <= high:
        if input_list[mid] == 0:
            input_list[low], input_list[mid] = input_list[mid], input_list[low]
            low += 1
            mid += 1
        elif input_list[mid] == 1:
            mid += 1
        else:
            input_list[mid], input_list[high] = input_list[high], input_list[mid]
            high -= 1
    return input_list

# Test Cases
print(sort_012([2, 0, 2, 1, 1, 0]))  # Outputs: [0, 0, 1, 1, 2, 2]

**References:**
- "Dutch National Flag Problem." Wikipedia, the free encyclopedia, [Dutch National Flag Problem on Wikipedia](https://en.wikipedia.org/wiki/Dutch_national_flag_problem). Accessed 21 May 2024.


**Solution:**

def sort_012(input_list):
    """
    Given an input array consisting of only 0, 1, and 2, sort the array in a single traversal.

    Args:
       input_list(list): List to be sorted
    """
    # Three pointers to keep track of the positions of 0, 1, and 2
    low = 0
    mid = 0
    high = len(input_list) - 1
    
    while mid <= high:
        if input_list[mid] == 0:
            input_list[low], input_list[mid] = input_list[mid], input_list[low]
            low += 1
            mid += 1
        elif input_list[mid] == 1:
            mid += 1
        else:
            input_list[mid], input_list[high] = input_list[high], input_list[mid]
            high -= 1
    
    return input_list

def test_function(test_case):
    sorted_array = sort_012(test_case)
    print(sorted_array)
    if sorted_array == sorted(test_case):
        print("Pass")
    else:
        print("Fail")

# Test cases
test_function([0, 0, 2, 2, 2, 1, 1, 1, 2, 0, 2])
test_function([2, 1, 2, 0, 0, 2, 1, 0, 1, 0, 0, 2, 2, 2, 1, 2, 0, 0, 0, 2, 1, 0, 2, 0, 0, 1])
test_function([0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2])

[0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2]
Pass
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Pass
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]
Pass

## Represents a single node in the Trie
class TrieNode:
    def __init__(self):
        """
        Initialize this node in the Trie
        """
        self.children = {}
        self.is_word = False
    
    def insert(self, char):
        """
        Add a child node in this Trie
        """
        if char not in self.children:
            self.children[char] = TrieNode()

## The Trie itself containing the root node and insert/find functions
class Trie:
    def __init__(self):
        """
        Initialize this Trie (add a root node)
        """
        self.root = TrieNode()
    
    def insert(self, word):
        """
        Add a word to the Trie
        """
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                current_node.insert(char)
            current_node = current_node.children[char]
        current_node.is_word = True
    
    def find(self, prefix):
        """
        Find the Trie node that represents this prefix
        """
        current_node = self.root
        for char in prefix:
            if char not in current_node.children:
                return None
            current_node = current_node.children[char]
        return current_node

## Now that we have a functioning Trie, we need to add the ability to list suffixes to implement our autocomplete feature.

class TrieNode:
    def __init__(self):
        """
        Initialize this node in the Trie
        """
        self.children = {}
        self.is_word = False
    
    def insert(self, char):
        """
        Add a child node in this Trie
        """
        if char not in self.children:
            self.children[char] = TrieNode()
    
    def suffixes(self, suffix=''):
        """
        Recursive function that collects the suffix for 
        all complete words below this point
        """
        suffix_list = []
        if self.is_word:
            suffix_list.append(suffix)
        
        for char, node in self.children.items():
            suffix_list.extend(node.suffixes(suffix + char))
        
        return suffix_list

## Testing it all out
MyTrie = Trie()
wordList = [
    "ant", "anthology", "antagonist", "antonym", 
    "fun", "function", "factory", 
    "trie", "trigger", "trigonometry", "tripod"
]
for word in wordList:
    MyTrie.insert(word)

from ipywidgets import widgets
from IPython.display import display
from ipywidgets import interact

def f(prefix):
    if prefix != '':
        prefixNode = MyTrie.find(prefix)
        if prefixNode:
            print('\n'.join(prefixNode.suffixes()))
        else:
            print(prefix + " not found")
    else:
        print('')

interact(f, prefix='');

def get_min_max(ints):
    """
    Return a tuple(min, max) out of list of unsorted integers.
    
    Args:
       ints(list): list of integers containing one or more integers
    """
    if not ints:
        return None, None  # Handle the case of an empty list
    
    # Initialize min and max to the first element
    min_val = ints[0]
    max_val = ints[0]
    
    # Iterate through the list and update min and max
    for num in ints:
        if num < min_val:
            min_val = num
        if num > max_val:
            max_val = num
    
    return min_val, max_val

# Example Test Case of Ten Integers
import random

l = [i for i in range(0, 10)]  # a list containing 0 - 9
random.shuffle(l)

print("Pass" if ((0, 9) == get_min_max(l)) else "Fail")
print("Pass" if ((1, 10) == get_min_max([3, 2, 1, 4, 5, 6, 7, 10, 8, 9])) else "Fail")
print("Pass" if ((-10, 10) == get_min_max([10, -10, 0, 5, -5])) else "Fail")
print("Pass" if ((1, 1) == get_min_max([1])) else "Fail")
print("Pass" if ((None, None) == get_min_max([])) else "Fail")

Pass
Pass
Pass
Pass
Pass

class RouteTrieNode:
    def __init__(self):
        self.children = {}
        self.handler = None

class RouteTrie:
    def __init__(self, root_handler):
        self.root = RouteTrieNode()
        self.root.handler = root_handler

    def insert(self, path_parts, handler):
        node = self.root
        for part in path_parts:
            if part not in node.children:
                node.children[part] = RouteTrieNode()
            node = node.children[part]
        node.handler = handler

    def find(self, path_parts):
        node = self.root
        for part in path_parts:
            if part in node.children:
                node = node.children[part]
            else:
                return None
        return node.handler

class Router:
    def __init__(self, root_handler, not_found_handler):
        self.route_trie = RouteTrie(root_handler)
        self.not_found_handler = not_found_handler

    def add_route(self, path, handler):
        path_parts = self.split_path(path)
        self.route_trie.insert(path_parts, handler)

    def lookup(self, path):
        path_parts = self.split_path(path)
        handler = self.route_trie.find(path_parts)
        if handler:
            return handler
        return self.not_found_handler

    def split_path(self, path):
        return [part for part in path.split('/') if part]

# Test Cases
router = Router("root handler", "not found handler")
router.add_route("/home/about", "about handler")
print(router.lookup("/"))  # Outputs: 'root handler'
print(router.lookup("/home"))  # Outputs: 'not found handler'
print(router.lookup("/home/about"))  # Outputs: 'about handler'

**References:**
- "Trie." Wikipedia, the free encyclopedia. [Trie on Wikipedia](https://en.wikipedia.org/wiki/Trie). Accessed 23 May 2024.


**Solution:**

## A RouteTrie will store our routes and their associated handlers
class RouteTrie:
    def __init__(self, root_handler):
        """
        Initialize the trie with a root node and a handler.
        """
        self.root = RouteTrieNode()
        self.root.handler = root_handler

    def insert(self, path, handler):
        """
        Add a handler for a path by inserting nodes.
        """
        parts = self.split_path(path)
        current_node = self.root
        for part in parts:
            if part not in current_node.children:
                current_node.children[part] = RouteTrieNode()
            current_node = current_node.children[part]
        current_node.handler = handler

    def find(self, path):
        """
        Find the handler for a given path.
        """
        parts = self.split_path(path)
        current_node = self.root
        for part in parts:
            if part not in current_node.children:
                return None
            current_node = current_node.children[part]
        return current_node.handler

    @staticmethod
    def split_path(path):
        """
        Split the path into parts.
        """
        return [part for part in path.split('/') if part]


## A RouteTrieNode will be similar to our autocomplete TrieNode... with one additional element: a handler.
class RouteTrieNode:
    def __init__(self):
        """
        Initialize the node with children and a handler.
        """
        self.children = {}
        self.handler = None


## The Router class will wrap the Trie and handle
class Router:
    def __init__(self, root_handler, not_found_handler):
        """
        Create a new RouteTrie for holding our routes and handlers.
        """
        self.route_trie = RouteTrie(root_handler)
        self.not_found_handler = not_found_handler

    def add_handler(self, path, handler):
        """
        Add a handler for a path.
        """
        self.route_trie.insert(path, handler)

    def lookup(self, path):
        """
        Lookup path (by parts) and return the associated handler.
        """
        if path == '/':
            return self.route_trie.root.handler

        handler = self.route_trie.find(path)
        if handler:
            return handler
        else:
            return self.not_found_handler

    def split_path(self, path):
        """
        Split the path into parts.
        """
        return self.route_trie.split_path(path)


## Testing the Router
# Here are some test cases and expected outputs you can use to test your implementation

# create the router and add a route
router = Router("root handler", "not found handler")  # remove the 'not found handler' if you did not implement this
router.add_handler("/home/about", "about handler")  # add a route

# some lookups with the expected output
print(router.lookup("/"))  # should print 'root handler'
print(router.lookup("/home"))  # should print 'not found handler' or None if you did not implement one
print(router.lookup("/home/about"))  # should print 'about handler'
print(router.lookup("/home/about/"))  # should print 'about handler' or None if you did not handle trailing slashes
print(router.lookup("/home/about/me"))  # should print 'not found handler' or None if you did not implement one

root handler
not found handler
about handler
about handler
not found handler

Problem 1: Square Root of an Integer¶

Finding the Square Root of an Integer¶

Problem 2: Search in a Rotated Sorted Array¶

Search in a Rotated Sorted Array¶

Problem 3: Rearrange Array Digits¶

Rearranging Array Digits to Form the Maximum Possible Numbers¶

Problem 4: Dutch National Flag Problem¶

Sorting 0s, 1s, and 2s in a Single Traversal¶

Problem 5: Autocomplete with Tries¶

Implementing Autocomplete with Tries¶

Problem 6: Unsorted Integer Array¶

Finding Max and Min in a Single Traversal¶

Problem 7: Request Routing in a Web Server with a Trie¶

Implementing Request Routing Using a Trie¶